package leetcode;

/**
 * @author Liangyaoyun
 */
public class rotateRight {
    public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            //判空，减少k或者head为消耗的时间
            if(k==0||head==null){
                return head;
            }
            //用来记录链表长度
            int len=0;
            //创建一个虚拟链表，代表尾节点
            ListNode tail=head;
            //获取链表长度
            for(ListNode p =head;p!=null;p=p.next){
                len++;
                tail=p;
            }
            //减少无效旋转，降低时间损耗
            k=k%len;
            //创建一个新的链表用来存储需要旋转部分的节点
            //就是不用放到前面的那部分节点
            ListNode pre=head;
            //找到链表的第len-k个节点
            //[3,4,5]
            for(int i=0;i<len-k-1;i++){
                pre=pre.next;
            }
            //将头结点[1]赋给tail
            tail.next=head;
            //将链表断开的后半部分设为头结点
            head=pre.next;
            //
            pre.next=null;
            return head;
        }
    }
}
